using System;
using System.Collections;
using Slaks.Graphs.Algorithms;

namespace Slaks.Graphs.ShenkerGraph.Algorithms
{
	public class ShenkerGraphClustering : ClusteringBase
	{
	    public ShenkerGraphClustering()
        {
        }

		public ShenkerGraphClustering(int numberOfClusters, GraphDistanceBase graphDistanceMeasure)
		{
			m_graphDistanceMeasure = graphDistanceMeasure.clone ();
			m_numberOfClusters = numberOfClusters;
		}       	

		private void Init( GraphList graphList )
		{
            if (graphList == null || graphList.Count == 0) throw new GraphException("There are no graphs in the list");
			if (m_numberOfClusters <= 0) throw new GraphException("Number of clusters must be greater then 0");
			if (graphList.Count < m_numberOfClusters) m_numberOfClusters = graphList.Count;
			m_graphClusters = new GraphList[m_numberOfClusters];
			for (int i = 0; i < m_numberOfClusters; i++)
			{
				m_graphClusters[i] = new GraphList();
			}

			int clusterNumber;
			Random rand = new Random(unchecked((int) DateTime.Now.Ticks));
			foreach (Graph graph in graphList)
			{
				clusterNumber = rand.Next(m_numberOfClusters);
				m_graphClusters[clusterNumber].Add(graph);
			}

			for (int i = 0; i < m_numberOfClusters; i++)
			{
				Graph graph;
				if (m_graphClusters[i].Count > 0)
				{
					graph = m_graphClusters[i][0];
					m_graphClusters[i].SetCentroid(graph);
				}
			}
		}

		
		/// <summary>
		/// Apply the Shenker Algorithm
		/// </summary>
        public override GraphList[] Apply(GraphList graphList)
		{
            this.Init( graphList );
			bool isChanged = true;
            
			while (isChanged == true)
			{
				isChanged = this.DetermineCentroids();
				//Console.WriteLine("determine :"  + this.CountGraphs());
				if (isChanged == true)
				{
                    this.AssignGraphs();
                    return m_graphClusters;
					//Console.WriteLine("apply :"  + this.CountGraphs());
				}
			}
            return null;
		}

		/// <summary>
		/// Determine centroids for clusters and return whether the centroids were changed
		/// </summary>
		/// <returns>true if centroids were altered otherwise return false</returns>
		private bool DetermineCentroids()
		{
			bool isChanged = false;
			bool result = false;
			foreach (GraphList graphCluster in m_graphClusters)
			{
				result = graphCluster.DetermineCentroid(m_graphDistanceMeasure);
				if (result == true) isChanged = true;
			}
            if (!result)
            {
                //check if to replace centroid
                foreach (GraphList cluster in m_graphClusters)
                {
                    GraphList candidateCluster = null;
                    var minDistance = Double.MaxValue;
                    foreach (GraphList newCluster in m_graphClusters)
                    {
                        if (cluster == newCluster) continue;
                        m_graphDistanceMeasure.firstGraph = cluster.GetCentroid();
                        m_graphDistanceMeasure.secondGraph = newCluster.GetCentroid();
                        var tempDistance = m_graphDistanceMeasure.GetDistance();
                        if (tempDistance < cluster.GetAverageDistanceToCentroid())
                        {
                            candidateCluster = newCluster;
                            minDistance = tempDistance;
                            
                        }
                    }
                    if (candidateCluster != null)
                    {
                        Graph centroid = cluster.GetCentroid();
                        candidateCluster.Add(centroid);
                        cluster.Remove(centroid);
                        ///find furthest node
                        Graph candidateCentroid = null;
                        var maxDistance = double.MinValue;
                        foreach (Graph graph in cluster)
                        {
                            m_graphDistanceMeasure.firstGraph = centroid;
                            m_graphDistanceMeasure.secondGraph = graph;
                            var tempDist = m_graphDistanceMeasure.GetDistance();
                            if (tempDist>maxDistance)
                            {
                                candidateCentroid = graph;
                                maxDistance = tempDist;
                            }
                        }
                        if (candidateCentroid!=null)
                        {
                            cluster.SetCentroid(candidateCentroid);
                        }
                        else
                        {
                            cluster.SetCentroid(null);
                        }
                        result = isChanged = true;
                    }
                }
            }
			return isChanged;
		}

		private void AssignGraphs()
		{
			double minDistance;
			double tempDistance;
			int cluster = 0;
			Graph centroid;
			Graph currentGraph;

			//holds graphs that must be removed
			ArrayList graphsToRemove = new ArrayList();
			for (int i = 0; i < m_graphClusters.Length; i++)
			{
			    var currentCentroid = m_graphClusters[i].GetCentroid();
				graphsToRemove.Clear();
				for (int j = 0; j < m_graphClusters[i].Count; j++)
				{
					minDistance = double.MaxValue;
					cluster = i; //current cluster to which currentGraph belongs
					currentGraph = m_graphClusters[i][j];

                    if (currentGraph == currentCentroid) continue;
                    
					for (int k = 0; k < m_graphClusters.Length; k++)
					{
						centroid = m_graphClusters[k].GetCentroid();
						if (centroid == null) continue;
                        m_graphDistanceMeasure.firstGraph = centroid;
                        m_graphDistanceMeasure.secondGraph = currentGraph;
						tempDistance = m_graphDistanceMeasure.GetDistance ();
						if (minDistance > tempDistance)
						{
							minDistance = tempDistance;
							cluster = k;
						}
					}
                    
					//the graph belongs to another cluster
					if (cluster != i)
					{
						m_graphClusters[cluster].AddGraphToTemporalList(currentGraph);
						graphsToRemove.Add(currentGraph);
					}
				} //end of for

				foreach (Graph graph in graphsToRemove)
				{
					m_graphClusters[i].Remove(graph);
				}

			} //end of for

			for (int i = 0; i < m_graphClusters.Length; i++)
			{
				m_graphClusters[i].MergeTemporalList();
			}

		}		
	}
}